#include<stdio.h>
#include<stdlib.h>

void merge_sort(int arr[],int n);
void msort(int arr[],int tempArr[],int left,int right);
void merge(int arr[],int tempArr[],int left,int mid,int right);
void print_Arr(int arr[],int n);
int main(){
    int arr[]={1,2,3,5,4,5,78,9};
    int n=8;
    merge_sort(arr,n);
    print_Arr(arr,n);
    return 0;
}

void print_Arr(int arr[],int n){
    for(int i=0;i<n;i++){
        printf("%d ",arr[i]);
    }
}
void merge(int arr[],int tempArr[],int left,int mid,int right){
    //标记左半部分第一个未排序元素
    int l_pos=left;
    //标记右半部分第一个未排序元素
    int r_pos=mid+1;
    //标记tempArr当前位置
    int pos=left;
    //合并
    while(l_pos<=mid && r_pos<=right){
        if(arr[l_pos]<arr[r_pos])
            tempArr[pos++]=arr[l_pos++];
        else
            tempArr[pos++]=arr[r_pos++];
    }
    //合并左剩余
    while(l_pos<=mid){
        tempArr[pos++]=arr[l_pos++];
    }
    //合并右剩余
    while(r_pos<=right){
        tempArr[pos++]=arr[r_pos++];
    }
    //arr <- tempArr
    while(left<=right){
        arr[left]=tempArr[left];
        left++;
    }
}
//归并排序，划分
void msort(int arr[],int tempArr[],int left,int right){
    //如果只有一个元素不需要划分,只需要被归并

    if(left<right){//不止一个元素
        int mid=(left+right)/2;
        msort(arr,tempArr,left,mid);//划分左半部分
        msort(arr,tempArr,mid+1,right);//划分右半部分
        //排序+合并
        merge(arr,tempArr,left,mid,right);
    }
}
//归并排序入口
void merge_sort(int arr[],int n){
    //分配一个辅助数组
    int *tempArr=(int*)malloc(n*sizeof(int));
    if(tempArr){
        msort(arr,tempArr,0,n-1);
        free(tempArr);
    }
}
